class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {

        int n = nums.size();
        if(n == 0) return {-1, -1};
        if(n == 1) return nums[0] == target? vector<int>{0, 0}: vector<int>{-1, -1};
        
        int left=-1, right=-1;
        int l=0, r=n-1;
        if(target < nums[l] || target > nums[r]) return {-1, -1};

        while(l <= r) {
            if(target == nums[l]){
                if(l > 0 && target == nums[l-1]){
                    l = l-1;
                }
                else{
                    left = l;
                }
            }
            if(target == nums[r]){
                if(r < n-1 && target == nums[r+1]){
                    r = r+1;
                }
                else{
                    right = r;
                }
            }
            if(left != -1 && right != -1) return{left, right};
            
            int mid = (l+r)/2;
            if(nums[mid] == target){
                if (target != nums[l]) l = mid;
                if (target != nums[r]) r = mid;
            }
            else if(target < nums[mid]){
                r = mid-1;
            }
            else{
                l = mid+1;
            }
        }
        return {-1, -1};

    }
};